#include "stdio.h"
#include "stdlib.h"

#define MAX(A,B) ((A)>(B)? (A):(B))
#define HEIGHT(node) (node == NULL ? -1:node->height)
typedef int elem_t;

typedef struct avl_node {
	elem_t elem;
	struct avl_node *left;
	struct avl_node *right;
	int height;		// 节点高度
} avl_t;

int update_height(avl_t *T) {
	return MAX(HEIGHT(T->left), HEIGHT(T->right)) + 1;
}

avl_t *avl_new_node(elem_t e, avl_t *left, avl_t *right) {
	avl_t *node = malloc(sizeof(*node));
	node->elem = e;
	node->left = left;
	node->right = right;
	node->height = 0;
	return node;
}



// 左子树不平衡，太高，右旋转
avl_t *LL(avl_t *T) {
	avl_t *L = T->left;	// 作为新的根
	T->left = L->right;	
	L->right = T;

	T->height = update_height(T);
	L->height = update_height(L);
	return L;
}
// 右子树不平衡，太高，左旋转
avl_t *RR(avl_t *T) {
	avl_t *R = T->right;	// 作为新的根
	
	T->right = R->left;	
	R->left = T;

	T->height = update_height(T);
	R->height = update_height(R);
	return R;
}

// 失衡位置在左子树的右节点
avl_t *LR(avl_t *T) {
	T->left = RR(T->left);
	return LL(T);
}

avl_t *RL(avl_t *T) {
	T->right = LL(T->right);
	return RR(T);
}

// 在插入节点后要保证树的平衡
avl_t *insert(avl_t *T, elem_t e) {
	if (T == NULL) 
		return avl_new_node(e, NULL, NULL);
	
	if (e < T->elem) {	// 往左子树中插入节点
		T->left = insert(T->left, e);
		if (HEIGHT(T->left) - HEIGHT(T->right) > 1) {
			if (e < T->left->elem)
				T = LL(T);
			else
				T = LR(T);
		}
	} else if (e > T->elem) {	// 往右子树中插入节点
		T->right = insert(T->right, e);
		if (HEIGHT(T->right) - HEIGHT(T->left) > 1) {
			if (e > T->right->elem)
				T = RR(T);
			else
				T = RL(T);
		}
	} 

	T->height = update_height(T);
	return T;
}
// 中序遍历，结果为升序数组
void in_order(avl_t *T) {
	if (T == NULL) return ;
	in_order(T->left);
	printf("%d ", T->elem);
	in_order(T->right);
}

avl_t *find(avl_t *T, elem_t e) {
	if (T == NULL) return NULL;
	if (e < T->elem) return find(T->left, e);
	else if (e > T->elem) return find(T->right, e);
	else return T;
}

// 找到最小节点，一直往左找
avl_t *min_node(avl_t *T) {
	if (T == NULL) return NULL;

	while (T->left != NULL) 
		T = T->left;
	return T;
}
avl_t *max_node(avl_t *T) {
	if (T == NULL) return NULL;

	while (T->right != NULL) 
		T = T->right;
	return T;
}

// 调用delete前，先调用find函数判断节点是否存在
avl_t *delete(avl_t *T, elem_t e) {
	if (T == NULL) return NULL;
	if (e < T->elem) {	// 删除节点在左子树
		T->left = delete(T->left, e);	
		// 删除后调整拓扑
		if (HEIGHT(T->right) - HEIGHT(T->left) > 1) {
			avl_t *temp = T->right;
			if (HEIGHT(temp->left) > HEIGHT(temp->right)) 
				T = RL(T);
			else 
				T = RR(T);
		} 
	} else if (e > T->elem) {	// 删除节点在右子树
		T->right = delete(T->right, e);	
		// 删除后调整拓扑
		if (HEIGHT(T->left) - HEIGHT(T->right) > 1) {
			avl_t *temp = T->left;
			if (HEIGHT(temp->right) > HEIGHT(temp->left)) 
				T = LR(T);
			else 
				T = LL(T);
		} 
	} else {	// 找到要删除的节点
		if (T->left && T->right) {
			// 右子树的最小节点或左子树的最大值 min替换当前节点，再删除min
			if (HEIGHT(T->right) > HEIGHT(T->left)) {
				avl_t *min = min_node(T->right);
				T->elem = min->elem;
				T->right = delete(T->right, min->elem);
			} else {
				avl_t *max = max_node(T->left);
				T->elem = max->elem;
				T->left = delete(T->left, max->elem);
			}
		} else {
			// 度不为2，则直接用左节点替换它的父节点
			T = T->left? T->left:T->right;
		}
	}
	if (T) T->height = update_height(T);
	return T;
}

int main() {
	// 构造AVL树测试
	elem_t arr[] = {12, 2, 6, 19, 8, 25};
	int len = sizeof(arr)/sizeof(arr[0]);
	avl_t *T = NULL;
	for (int i = 0; i < len; i++) {
		T = insert(T, arr[i]);
	}
	in_order(T);
	
	// 删除测试
	avl_t *temp = NULL;
	elem_t delte = (elem_t)25;
	if ( (temp = find(T, delte)) != NULL)
		printf("\nfind %d success\n", temp->elem);
	T = delete(T, delte);
	in_order(T);
	
	return 0;
}